1. Field of the Invention
The present invention relates to techniques for managing data flow in communication systems. More specifically, the present invention relates to a technique for reordering data packets in a queue to provide increased utility without reducing existing fairness between independent data streams.
2. Related Art
The recent proliferation of communication systems and networks, and the associated advances in networking technology, are enabling a wide variety of new services and applications. For example, users are now able to view time-based media (such as audio and/or video) that is streamed in real-time over communication networks. However, many of these communication networks are lossy. This is particularly the case in those networks that implement increasingly popular consumer-networking technologies, such as the Internet. In these communication networks, information in the form of data packets may be lost during transmission. As a consequence, data packets may need to be retransmitted to ensure proper reception. Furthermore, even if data packets are not lost during transmission, the data packets may arrive in a different order than their original sequential order.
Delivering data packets out of order can have a detrimental effect on the performance of communication protocols. Communication protocols such as Transmission Control Protocol (TCP) achieve high performance by having multiple data packets in flight at the same time. For example, it is not uncommon for a TCP connection to have as many as 40 unacknowledged data packets outstanding at any one time. As the first of these data packets arrive at the receiver and are acknowledged, the sender transmits more data packets to maintain a pipeline of data packets in flight. If a single data packet is lost, the sender's TCP stack will promptly retransmit the lost data packet, but in a first-come-first-served network, this retransmitted data packet will be stuck in a long queue behind 40 other data packets. Thus, while the retransmitted data packet is conceptually ahead of the other 40 data packets from the perspective of TCP, it is chronologically behind these other data packets from the network-hardware perspective.
Because of the way TCP is designed, the sender's TCP stack cannot usefully deliver out-of-order data to the client. As a result, it has to save those 40 other data packets in buffers until the waited-for retransmitted data packet arrives to fill the gap in the sequence, and then the entire contiguous batch of data can be delivered to the client. Furthermore, even though a relatively steady stream of inbound data packets was received at the IP layer, from the client's point of view the data arrival rate is erratic and bursty. For example, sometimes no data is delivered for a long time (in computer terms, perhaps a whole second), and then a large burst of data is delivered all at once.
With time-based media, like audio or video, this bursty delivery is undesirable. Even though the lost data packet was retransmitted promptly by TCP, the retransmitted data packet was stuck at the back of a long queue, and by the time it finally arrives, the receiver may have already passed the time when that media was supposed to be played, resulting in audio dropouts and visual glitches. Because such audio dropouts and visual glitches are unacceptable, the receiver has to be engineered to withstand such delays, for example, by using larger playback buffers to absorb the variability. These larger playback buffers increase the cost of the device, and decrease the responsiveness of the user interface because it takes longer to fill these larger playback buffers.
Even for non-time-based data, such as a simple file transfer, having retransmitted data packets stuck at the back of a long queue is undesirable. For example, the amount of unacknowledged TCP data that a sender can have outstanding at any time is limited by the ‘receive window’ offered by the receiver. When a data packet is lost, all subsequent data packets take up space in that receive window, and when the entire receive window is consumed, the sender is prohibited from sending any more data until the awaited retransmitted data packet is received and acknowledged by the receiver. These pauses that are imposed on the sender result in lower overall aggregate throughput. This means that even for non-time-based data, having retransmitted data packets stuck at the back of a long queue can result in reduced throughput.
Furthermore, regardless of whether data is time-based or not, bursty delivery is undesirable for other reasons too. For example, during the times that the TCP stack delivers no data to the client, system resources like the CPU, memory bandwidth, and disk bandwidth may be under-utilized. Then, when a large burst of data is delivered, those system resources are suddenly over-taxed until the large burst of data has been processed. Suppose for example that the limiting factor in a file transfer is the speed data can be written to a hard disk drive. When a data packet is lost and the receiver's TCP stack stops delivering data while it waits for a retransmission of the lost data packet, the disk drive may complete all its outstanding writes and go idle. Then, when the retransmitted data packet arrives and the large burst of data is delivered, the disk drive will again become the bottleneck and the rate the client can accept the large burst of data from the TCP stack will be limited by how fast the disk drive can write the data. Consequently, each time the disk drive is allowed to go idle will be reflected as additional delays in the total time it takes to complete the entire file transfer. Therefore, smooth steady delivery of data is better than erratic or bursty delivery of data.
Several alternative communication protocols have been proposed to address these challenges. However, many of these protocols are complicated and expensive. Furthermore, these communication protocols may not be backwards compatible and may introduce new problems. For example, some existing communication protocols mark retransmitted data packets for special handling using a high-priority flag. Unfortunately, implementing high-priority flags requires coordination across multiple layers of software and between multiple components in the communication network. In addition, it is hard to prevent abuse of such a mechanism. As a consequence, high-priority flags may lead to fairness problems because users may ‘game’ the system to ensure that their data packets receive higher priority.
Hence what is needed is a method and an apparatus that facilitates the management of data flow in communication systems without the above-described problems.